題目連結: Valid Palindrome

題目描述為給定一字串 s，忽略英文字母與數字以外的字元，要我們判定此字串是否為回文。
題目有補充說明: 空字串視為回文，而且輸入的字串 s 只包含可以印出的ASCII字元。
例子 1 : s:="A man, a plan, a canal: Panama", output= true。
例子 2 : s:="race a car", output= false。

思路 1 : 排除可忽略字元

我們可以宣告一組 []byte，先排除可以忽略的字元，只保留英文字母(都轉換成小寫)與數字，再進行比較。

• 複雜度評估
  當字串長度為 N 時，只存英文字母與數字需要遍歷字串一次，比較是否為回文需要遍歷所存的 []byte 一次，時間複雜度為 O(N)。
  此方法另外宣告一組 []byte 存需要保留的字元，空間複雜度為 O(N)。

參考程式碼

func isPalindrome(s string) bool {
   
    bs:=[]byte{}
    var b byte
    for _,v:=range s{
        b=byte(v)
        if isAlphabet(b) || isNumeric(b){
            bs=append(bs,convertToLowerCase(b))
        }
    } 
    
    
    head:=0
    tail:=len(bs)-1
    
    for head<tail{
        if bs[head]!=bs[tail]{
            return false
        }
        
        head++
        tail--
    }
        
        
    return true

}

func isAlphabet( b byte) bool{
    if b>='a' && b<='z'{
        return true
    }
    
    if b>='A' && b <= 'Z'{
        return true
    }
    
    return false
}


func isNumeric( b byte) bool{
    if b>='0' && b<='9' {
        return true
    }
    return false
}

func convertToLowerCase( b byte) byte{
    
    if b>='A' && b <='Z'{
        b=b-'A'+'a'
    }
    
    return b
    
}

思路 2 : 直接處理

我們也可以直接進行比較，遇到可以忽略的字元則直接跳過。

• 複雜度評估
  當字串長度為 N 時，只存英文字母與數字需要遍歷字串一次，時間複雜度為 O(N)。
  此方法只使用常數個變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func isPalindrome(s string) bool {
    head:=0
    tail:=len(s)-1
    
    for head<tail{     
        if  !isAlphabet(s[head])&& !isNumeric(s[head]){
            head ++
            continue
        }   
        if  !isAlphabet(s[tail])&& !isNumeric(s[tail]){
            tail --
            continue
        }
        if convertToLowerCase(s[head])!=convertToLowerCase(s[tail]){
            return false
        }
            
        head++
        tail--
    }
        
        
    return true

}

func isAlphabet( b byte) bool{
    if b>='a' && b<='z'{
        return true
    }
    
    if b>='A' && b <= 'Z'{
        return true
    }
    
    return false
}


func isNumeric( b byte) bool{
    if b>='0' && b<='9' {
        return true
    }
    return false
}

func convertToLowerCase( b byte) byte{
    
    if b>='A' && b <='Z'{
        b=b-'A'+'a'
    }
    
    return b
    
}

小結

方法 1 與 方法 2 共用了輔助函式。
方法 1 也可宣告 []rune 來儲存需保留字元，此時則不需要在儲存時將 rune 轉換成 byte type，但注意需要修改輔助函式的 input/output type。
Go語言中 byte 與 rune 的說明詳見 GOLANG TUTORIAL - BYTE AND RUNE。
以下引述文章中的內容，最明顯的差異為可表示的字元: "The byte data type represents ASCII characters while the rune data type represents a more broader set of Unicode characters that are encoded in UTF-8 format."

我將解法1、2加上簡單的測試，上傳程式碼到此。